#include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <string>  
#include <limits.h>  
using namespace std;  
int dpx[1100][110],p[1100][1100],s[1100],dp[1100][1100];  
int anx,any;  
int main()  
{  freopen("in", "r", stdin);
   int n;  
   while(cin>>n)  
   {  
       memset(p,0,sizeof(p));  
       for(int i=1;i<=n;i++)  
       {  
           cin>>s[i];  
           s[n+i]=s[i];  
       }  
       for(int i=1;i<=2*n;i++)  
        {  
            p[i][i]=s[i];  
            for(int j=i+1;j<=2*n;j++)  
                p[i][j]=p[i][j-1]+s[j];  
        }  
    for(int i = 1; i <= n << 1; i++) { 
        for(int j = i + 1; j <= n << 1; j++) { 
            cout << p[i][j] << " ";
        }
        cout << '\n';
    }
       memset(dp,0,sizeof(dp));  
       for(int r=1;r<n;r++)     //r 表示待合并进来的石子个数  
       {  
           for(int i=1;i<=2*n-r;i++) //i表示合并石子，起始位置  
           {  
               int j=r+i;      //j表示要合并r个石子，合并序列结束的位置  
               dpx[i][j]=INT_MAX;  //初始化  
               for(int k=i;k<j;k++)  
               {  
                   dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+p[i][j]);  
                   dpx[i][j]=min(dpx[i][j],dpx[i][k]+dpx[k+1][j]+p[i][j]);  
               }  
           }  
       }  
       anx=0;  
       any=INT_MAX;  
       for(int i=1;i<=n;i++) //2N堆中，求解所有长度为N的连续序列合并最大，最小值  
       {  
          anx=max(anx,dp[i][n+i-1]);  
          any=min(any,dpx[i][n+i-1]);  
       }  
       printf("%d\n",any);  
       printf("%d\n",anx);  
   }  
   return 0;  
}  
